package leetcode.code1834;

import java.util.Arrays;
import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.H;

/**
 * 给你一个二维数组 tasks ，用于表示 n​​​​​​ 项从 0 到 n - 1 编号的任务。 </br>
 * 其中 tasks[i] = [enqueueTimei, processingTimei] </br>
 * 意味着第 i​​​​​​​​​​ 项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。
 * 
 * 现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：
 * 
 * 如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。 </br>
 * 如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择执行时间最短的任务开始执行。</br>
 * 如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。 </br>
 * 一旦某项任务开始执行，CPU 在 执行完整个任务 前都不会停止。 </br>
 * CPU 可以在完成一项任务后，立即开始执行一项新任务。 返回 CPU 处理任务的顺序。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/single-threaded-cpu
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 **/
/**
 * 补充说明： 任务先入队，再执行。
 */

public class Solution implements IDebug {

	public int[] getOrder(int[][] tasks) {
		int len = tasks.length;
		int[][] tasksIdx = new int[len][3];
		for (int i = 0; i < tasksIdx.length; i++) {
			tasksIdx[i][0] = tasks[i][0];
			tasksIdx[i][1] = tasks[i][1];
			tasksIdx[i][2] = i;
		}
		Arrays.sort(tasksIdx, (a, b) -> a[0] - b[0]);
		int time = 0;
		// int[]{执行时间，index}
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
		int p = 0;
		int[] ans = new int[len];
		int ansp = 0;
		while (p < len) {
			while (p < len && tasksIdx[p][0] <= time) {
				queue.add(new int[] { tasksIdx[p][1], tasksIdx[p][2] });
				p++;
			}
			if (queue.isEmpty()) {
				time = tasksIdx[p][0];
			} else {
				int[] cur = queue.poll();
				ans[ansp++] = cur[1];
				time += cur[0];
			}
		}
		while (!queue.isEmpty()) {
			ans[ansp++] = queue.poll()[1];
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(H.str2array3("[15,14,13,1,6,3,5,12,8,11,9,4,10,7,0,2]"), this.getOrder(H.str2array1(
				"[[35,36],[11,7],[15,47],[34,2],[47,19],[16,14],[19,8],[7,34],[38,15],[16,18],[27,22],[7,15],[43,2],[10,5],[5,4],[3,11]]")));
		H.compare(H.str2array3("[6,1,2,9,4,10,0,11,5,13,3,8,12,7]"), this.getOrder(H.str2array1(
				"[[19,13],[16,9],[21,10],[32,25],[37,4],[49,24],[2,15],[38,41],[37,34],[33,6],[45,4],[18,18],[46,39],[12,24]]")));
		H.compare(H.str2array3("[4,3,2,0,1]"), this.getOrder(H.str2array1("[[7,10],[7,12],[7,5],[7,4],[7,2]]")));
		H.compare(H.str2array3("[0,2,3,1]"), this.getOrder(H.str2array1("[[1,2],[2,4],[3,2],[4,1]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
